The statement we want to prove is equivalent to the following. Given a graph $G = (V,E)$, a matching $M \subseteq E$ is not maximum if and only if there is an augmenting path in $G$ with respect to $M$. There are two directions to prove.

First direction: Suppose there is an augmenting path in $G$ with respect to $M$. Then we want to show that $M$ is not maximum. Let the augmenting path be $v_1,v_2,\ldots,v_k$:

The highlighted edges represent edges in $M$. By the definition of an augmenting path, we know that $v_1$ and $v_k$ are not matched by $M$. Since $v_1$ and $v_k$ are not matched and the path is alternating, the number of edges on this path that are in the matching is one less than the number of edges not in the matching. To see that $M$ is not a maximum matching, observe that we can obtain a bigger matching by flipping the matched and unmatched edges on the augmenting path. In other words, if an edge on the path is in the matching, we remove it from the matching, and if an edge on the path is not in the matching, we put it in the matching. This gives us a matching larger than $M$, so $M$ is not maximum.

Second direction: We now prove the other direction. In particular, we want to show that if $M$ is not a maximum matching, then we can find an augmenting path in $G$ with respect to $M$. Since $M$ is not a maximum, there is a matching with larger size. Let $M^*$ be a matching such that $|M^*| > |M|$. We define the set $S$ to be the set of edges contained in $M^*$ or $M$, but not both. That is, $S = (M^* \cup M) \backslash (M^* \cap M)$ (this is the symmetric difference of $M^*$ and $M$). If we color the edges in $M$ with blue, and the edges in $M^*$ with red, then $S$ consists of edges that are colored either blue or red, but not both (i.e. no purple edges). Below is an example:

(Horizontal edges correspond to the red edges. The rest is blue.) Our goal is to find an augmenting path with respect to $M$ in $S$ (i.e., with respect to the blue edges), and once we do this, the proof will be complete.

We now proceed to find an augmenting path with respect to $M$ in $S$. To do so, we make a couple of important observations about $S$. First, notice that each vertex that is a part of $S$ has degree $1$ or $2$ because it can be incident to at most one edge in $M$ and at most one edge in $M^*$. (If the degree was more than $2$, either two edges from $M$ or two edges from $M^*$ would be intersecting, but in a matching, edges cannot intersect.) We now make two claims:

1. Because every vertex has degree $1$ or $2$, $S$ consists of disjoint paths and cycles (i.e. each connected component is either a path or a cycle).

   

2. The edges in these paths and cycles alternate between blue and red.

The proof of the first claim is omitted and is left as an exercise for the reader. The second claim is true because if the edges were not alternating, i.e., if there were two red or two blue edges in a row, then this would imply the red edges or the blue edges do not form a matching (remember that in a matching no two edges can share an endpoint).

Since $M^*$ is a bigger matching than $M$, we know that $S$ has more red edges than blue edges. Observe that the cycles in $S$ must have even length, because otherwise the edges cannot alternate between blue and red. Therefore the cycles have an equal number of red and blue edges. This implies that there must be a path in $S$ with more red edges than blue edges. In particular, this path starts and ends with a red edge. This path is an augmenting path with respect to $M$ (i.e., the blue edges), since it is clearly alternating between edges in $M$ and edges not in $M$, and the endpoints are unmatched with respect to $M$. So using the assumption that $M$ is not maximum, we were able to find an augmenting path with respect to $M$. This completes the proof.

There are two directions to prove.

($\Longrightarrow$): For this direction, we want to show that if a graph is bipartite, then it contains no odd-length cycles. We prove the contrapositive. Observe that it is impossible to $2$-color an odd-length cycle. So if a graph contains an odd-length cycle, the graph cannot be $2$-colored, and therefore cannot be bipartite.

($\Longleftarrow$): For this direction, we want to show that if a graph does not contain an odd-length cycle, then it is bipartite. So suppose the graph contains no cycles of odd length. Without loss of generality, assume the graph is connected (if it is not, we can apply the argument to each connected component separately). For $u,v \in V$, let $\text{dist}(u,v)$ denote the length of the shortest path from $u$ to $v$ (or from $v$ to $u$). Pick a starting vertex/root $s$ and consider the “BFS tree” rooted at $s$. In this tree, level 0 corresponds to $s$, and level $i$ corresponds to all vertices $v$ with $\text{dist}(s,v) = i$. Color odd-indexed levels blue, and color even-indexed levels red.

The proof is done once we show that this is a valid $2$-coloring of the graph. To show this, we’ll argue that no edge has its endpoints colored the same color. There are two types of edges we need to worry about that could potentially have its endpoints colored the same color. We consider each type below.

First, there could potentially be an edge between two vertices $u$ and $v$ at the same level. Let’s assume such an edge exists. Let $w$ be the lowest common ancestor of $u$ and $v$. Note that $\text{dist}(u,w) = \text{dist}(v,w)$, so the path from $w$ to $u$, plus the path from $w$ to $v$, plus the edge $\{u,v\}$, form an odd-length cycle. This is a contradiction.

Second, we need to consider the possibility that there is an edge between a vertex $u$ at level $i$ and a vertex $v$ at level $i + 2k$ for some $k > 0$. However, the existence of such an edge implies that $\text{dist}(s,v) \leq i+1$, which contradicts the fact that $v$ is at level $i+2k$. So this type of edge cannot exist either. This completes the proof.

Let $G=(X,Y,E)$ be the input graph. The high level steps of the algorithm is as follows.

• Let $M = \{ \{x,y\} \}$ where $\{x,y\} \in E$ is an arbitrary edge.

• Repeat until there is no augmenting path with respect to $M$:

  • Find an augmenting path with respect to $M$.

  • Update $M$ according to the augmenting path (swapping matched and unmatched edges along the path).

Every time we find an augmenting path, we increase the size of our matching by one. When there are no more augmenting paths, we stop and correctly output a maximum matching (the correctness follows from Theorem (Characterization for maximum matchings)). The only unclear step of the algorithm is finding an augmenting path with respect to $M$. And we explain how to do this step below. But before we do that, note that if this step can be done in polynomial time, then the overall running time of the algorithm is polynomial time since the loop repeats $O(n)$ times and the work done in each iteration is polynomial time.

We now show how to find an augmenting path (given $G = (X,Y,E)$ and $M \subseteq E$). We first turn $G$ into a directed graph $\vec{G}$ as follows:

• Direct edges in $E \backslash M$ from $X$ to $Y$.

• Direct edges in $M$ from $Y$ to $X$.

Note that an alternating path with respect to $M$ in $G$ corresponds to a directed path in $\vec{G}$. (We leave it to the reader to verify this.) This means that there is an augmenting path with respect to $M$ in $G$ if and only if there is a directed path in $\vec{G}$ from an unmatched vertex $x$ in $X$ to an unmatched vertex $y$ in $Y$. So to find an augmenting path, we’ll search for a directed path in $\vec{G}$ from an unmatched $x$ to an unmatched $y$, as follows:

• For each unmatched $x \in X$:

  • Run DFS($\vec{G}$, $x$).

  • If you hit an unmatched $y \in Y$, output the path from $x$ to $y$.

• Output “no augmenting path found.”

The running time is polynomial time since the loop repeats at most $O(n)$ times, and the work done in each iteration is polynomial time.

There are two directions to prove.

($\Longrightarrow$): For this direction, we need to show that if $G$ has a matching covering all the vertices in $X$, then every $S \subseteq X$ satisfies $|S| \leq |N(S)|$. We consider the contrapositive. So suppose there is some $S \subseteq X$ such that $|S| > |N(S)|$. The vertices in $S$ can only be matched to vertices in $N(S)$, and since $|S| > |N(S)|$, there cannot be a matching that covers every element in $S$. And this implies there cannot be a matching covering every element of $X$.

($\Longleftarrow$): For this direction, we need to show that if every $S \subseteq X$ satisfies $|S| \leq |N(S)|$, then there is a matching that covers all the vertices in $X$. We will prove the contrapositive. So assume there is no matching that covers all the vertices in $X$. Our goal is to find some $S \subseteq X$ such that $|S| > |N(S)|$.

In order to identify such a set $S$, we need to make a couple of definitions. Let $M$ be a maximum matching and let $x \in X$ be an element that it does not cover. We turn $G$ into a directed graph as follows: direct all edges not in $M$ from $X$ to $Y$, and direct all edges in $M$ from $Y$ to $X$. We define $L \subseteq X$ to be the set of vertices in $X$ that you can reach by a directed path starting at $x$ ($L$ does not include $x$). And we define $R \subseteq Y$ to be the set of all vertices in $Y$ that you can reach by a directed path starting at $x$. Here is an illustration:

We will show that for $S = L \cup \{x\}$, we have $|S| > |N(S)|$. We need two claims to argue this.

Claim 1: $|L| = |R|$.
Proof: Each $\ell \in L$ is matched to some $r \in R$ because the only way we can reach an $\ell \in L$ is through an edge in the matching. Conversely, each $r \in R$ must be matched to some $\ell \in L$ since if this was not true, i.e., if there was an unmatched $r \in R$, that would imply that the path from $x$ to $r$ is an augmenting path, and this would contradict the fact that $M$ is a maximum matching (Theorem (Characterization for maximum matchings)). Since every element of $L$ is matched by $M$ to an element of $R$ and vice versa, there is a one-to-one correspondence between $L$ and $R$, i.e., $|L| = |R|$.

Claim 2: In the original undirected graph, $N(L \cup \{x\}) \subseteq R$.
(In fact, $N(L \cup \{x\}) = R$ but we only need one side of the inclusion.)
Proof: For any $\ell \in L \cup \{x\}$, we want to argue that $N(\ell) \subseteq R$. First consider the case that $\ell = x$. Then all the neighbors of $x$ must be in $R$ since all the edges incident to $x$ are directed from left to right. So $N(x) \subseteq R$. Now consider any $\ell \in L$. We want to argue that all the neighbors of $\ell$ must be in $R$. To argue about the neighbors of $\ell$, we look at all the edges incident to $\ell$. In this set of edges incident to $\ell$, exactly one edge $e$ is in the matching $M$. Since $e \in M$ is directed from $Y$ to $X$, it must be incident to some $r \in R$ because the only way to reach $\ell$ is through some $r \in R$ via $e$. If we now look at all the other edges incident to $\ell$, note that they must be directed from $X$ to $Y$, and the vertices $K \subseteq Y$ that they are incident to must be in $R$. This is because by definition of $L$, $\ell \in L$ is reachable from $x$, which means the vertices in $K$ would also be reachable from $x$, and therefore would be in $R$ (by the definition of $R$). This shows that every neighbor of $\ell$ is in $R$, and completes the proof of Claim 2.

Combining Claim 1 and Claim 2 above, we have $$|L \cup \{x\}| > |R| \geq |N(L \cup \{x\})|,$$ i.e., for $S = L \cup \{x\}$, $|S| > |N(S)|$, as desired.